{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 154,
   "id": "8b9d3522",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import math\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6cb67e25",
   "metadata": {},
   "outputs": [],
   "source": [
    "data_table = pd.DataFrame([\n",
    "    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '密度': 0.697, '含糖量': 0.460, '好瓜': '是'},\n",
    "    {'色泽': '乌黑', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '密度': 0.774, '含糖量': 0.376, '好瓜': '是'},\n",
    "    {'色泽': '乌黑', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '密度': 0.634, '含糖量': 0.264, '好瓜': '是'},\n",
    "    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '密度': 0.608, '含糖量': 0.318, '好瓜': '是'},\n",
    "    {'色泽': '浅白', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '密度': 0.556, '含糖量': 0.215, '好瓜': '是'},\n",
    "    {'色泽': '青绿', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '软粘', '密度': 0.403, '含糖量': 0.237, '好瓜': '是'},\n",
    "    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '稍糊', '脐部': '稍凹', '触感': '软粘', '密度': 0.481, '含糖量': 0.149, '好瓜': '是'},\n",
    "    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '硬滑', '密度': 0.437, '含糖量': 0.211, '好瓜': '是'},\n",
    "    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '沉闷', '纹理': '稍糊', '脐部': '稍凹', '触感': '硬滑', '密度': 0.666, '含糖量': 0.091, '好瓜': '否'},\n",
    "    {'色泽': '青绿', '根蒂': '硬挺', '敲声': '清脆', '纹理': '清晰', '脐部': '平坦', '触感': '软粘', '密度': 0.243, '含糖量': 0.267, '好瓜': '否'},\n",
    "    {'色泽': '浅白', '根蒂': '硬挺', '敲声': '清脆', '纹理': '模糊', '脐部': '平坦', '触感': '硬滑', '密度': 0.245, '含糖量': 0.057, '好瓜': '否'},\n",
    "    {'色泽': '浅白', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '模糊', '脐部': '平坦', '触感': '软粘', '密度': 0.343, '含糖量': 0.099, '好瓜': '否'},\n",
    "    {'色泽': '青绿', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '稍糊', '脐部': '凹陷', '触感': '硬滑', '密度': 0.639, '含糖量': 0.161, '好瓜': '否'},\n",
    "    {'色泽': '浅白', '根蒂': '稍蜷', '敲声': '沉闷', '纹理': '稍糊', '脐部': '凹陷', '触感': '硬滑', '密度': 0.657, '含糖量': 0.198, '好瓜': '否'},\n",
    "    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '软粘', '密度': 0.360, '含糖量': 0.370, '好瓜': '否'},\n",
    "    {'色泽': '浅白', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '模糊', '脐部': '平坦', '触感': '硬滑', '密度': 0.593, '含糖量': 0.042, '好瓜': '否'},\n",
    "    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '稍糊', '脐部': '稍凹', '触感': '硬滑', '密度': 0.719, '含糖量': 0.103, '好瓜': '否'}\n",
    "], columns=['色泽','根蒂','敲声','纹理','脐部','触感','密度','含糖量','好瓜'])\n",
    "att = {'色泽': 0, '根蒂': 0, '敲声': 0, '纹理': 0, '脐部': 0, '触感': 0}\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "id": "0907c7da",
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(data):\n",
    "    #计算信息熵\n",
    "    counter = Counter(data['好瓜'])\n",
    "    s = sum(counter.values())\n",
    "    return sum([-p/s * math.log(p/s, 2) for p in counter.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "id": "153a7d35",
   "metadata": {},
   "outputs": [],
   "source": [
    "def info_gain(data, attr, ent):\n",
    "    #计算信息增益\n",
    "    counter = Counter(data[attr])\n",
    "    gain = 0\n",
    "    for i in counter:\n",
    "        gain += entropy(data.loc[data[attr]==i]) * counter[i] / len(data)\n",
    "        # print(gain)\n",
    "    return ent - gain "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "id": "b5aabd72",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9975025463691153\n",
      "0.10812516526536531\n"
     ]
    }
   ],
   "source": [
    "ent = entropy(data_table)\n",
    "print(ent)\n",
    "counter = Counter(data_table['色泽'])\n",
    "print(info_gain(data_table, '色泽', ent))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "id": "3333ad13",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tree(root):\n",
    "    return [root, []]\n",
    "def set_child(parent, child):\n",
    "    parent.append(child)\n",
    "def set_choice(parent):\n",
    "    return parent.append([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "id": "f4a18cc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def node(m_root, data, att):\n",
    "    counter = Counter(data[m_root[0]])\n",
    "    for i in counter:\n",
    "        data1 = data[data[m_root[0]] == i]\n",
    "        if len(data) == 0:\n",
    "            return\n",
    "        if len(att) == 0:\n",
    "            return\n",
    "        counter1 = Counter(data1['好瓜'])\n",
    "        if counter1['是'] == 0:\n",
    "            m_root[-1].append(i+'坏瓜')\n",
    "            set_choice(m_root)\n",
    "            return\n",
    "        elif counter1['否'] == 0:\n",
    "            m_root[-1].append(i+'好瓜')\n",
    "            set_choice(m_root)\n",
    "            return\n",
    "        ent = entropy(data1)\n",
    "        gain = -1\n",
    "        root = ''\n",
    "        for i in att.keys():\n",
    "            if gain < info_gain(data1, i, ent):\n",
    "                root = i\n",
    "                gain = info_gain(data1, i, ent)\n",
    "        m_root[-1].append(root)\n",
    "        m_root[-1].append([])\n",
    "        att.pop(root)\n",
    "        node(m_root[-1], data1, att)\n",
    "    node(m_root,m_root, data=data, att=att)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "id": "6870530a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def TreeGenerator(att, data_table):\n",
    "    ent = entropy(data_table)\n",
    "    gain = -1\n",
    "    root = ''\n",
    "    for i in att.keys():\n",
    "        if gain < info_gain(data_table, i, ent):\n",
    "            root = i\n",
    "            gain = info_gain(data_table, i, ent)\n",
    "    Atree = tree(root)\n",
    "    att.pop(root)\n",
    "    node(Atree, data_table, att)\n",
    "    return Atree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "826c2417",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "id": "f9d04799",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['纹理', ['根蒂', ['蜷缩好瓜'], [], '触感', ['色泽', ['敲声', ['浊响好瓜'], [], '青绿坏瓜'], [], '蜷缩坏瓜'], [], '模糊坏瓜'], []]\n"
     ]
    }
   ],
   "source": [
    "a = TreeGenerator(att, data_table)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "id": "e9d3f4e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def p(a):\n",
    "    for i in a:\n",
    "        if isinstance(i, list):\n",
    "            p(i)\n",
    "            print()\n",
    "        else:\n",
    "            print(i, end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "id": "7c88bd12",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "纹理 根蒂 蜷缩好瓜 \n",
      "\n",
      "触感 色泽 敲声 浊响好瓜 \n",
      "\n",
      "青绿坏瓜 \n",
      "\n",
      "蜷缩坏瓜 \n",
      "\n",
      "模糊坏瓜 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "p(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "bcd7fa01",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "蜷缩\n",
      "稍蜷\n",
      "硬挺\n"
     ]
    }
   ],
   "source": [
    "counter = Counter(data_table['根蒂'])\n",
    "for i in counter:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "id": "1c52dbdb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['fff', []]\n"
     ]
    }
   ],
   "source": [
    "a = tree('fff')\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7351e8eb",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a78b02a1",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "303d70b0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "mining",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
